package leetcode;

public class LeetCode28 {

    public static void main(String[] args) {
        LeetCode28 leetCode28 = new LeetCode28();
        System.out.println(leetCode28.strStr2("hello", "ll"));
    }

    public int strStr1(String haystack, String needle) {
        if (needle.equals(""))
            return 0;
        //substr是左开右闭的
        int i = 0, j = needle.length();
        //substring会比较每一位的char
        while (j <= haystack.length()) {
            //数组遍历 equals也需要遍历
            if (haystack.substring(i++, j++).equals(needle))
                return i - 1;
        }
        return -1;
    }

    public int strStr2(String haystack, String needle) {
        if (needle.equals(""))
            return 0;
        int i = 0, length = needle.length();
        while (i <= haystack.length() - length) {
            int x = i, y = 0;
            while (y < needle.length()) {
                if (haystack.charAt(x) != needle.charAt(y))
                    break;
                else {
                    x++;
                    y++;
                }
            }
            if (y == needle.length() - 1) {
                return i;
            }
            i++;
        }
        return -1;
    }

    public int strStr(String haystack, String needle) {
        return haystack.indexOf(needle);
    }
//------------------------------------------------------------------

    public int strStr3(String haystack, String needle) {
        int L = needle.length(), n = haystack.length();
        if (L == 0) return 0;

        int pn = 0;
        while (pn < n - L + 1) {
            //解决只有一位比较的问题  先比较第一位 第一位一样再比较下一位
            while (pn < n - L + 1 && haystack.charAt(pn) != needle.charAt(0)) ++pn;

            int currLen = 0, pL = 0;
            while (pL < L && pn < n && haystack.charAt(pn) == needle.charAt(pL)) {
                ++pn;
                ++pL;
                ++currLen;
            }

            if (currLen == L) return pn - L;
            pn = pn - currLen + 1;
        }
        return -1;
    }

    // ？？？？
    public int charToInt(int idx, String s) {
        return (int)s.charAt(idx) - (int)'a';
    }

    public int strStr4(String haystack, String needle) {
        int L = needle.length(), n = haystack.length();
        if (L > n) return -1;

        // base value for the rolling hash function
        int a = 26;
        // modulus value for the rolling hash function to avoid overflow
        long modulus = (long)Math.pow(2, 31);

        // compute the hash of strings haystack[:L], needle[:L]
        long h = 0, ref_h = 0;
        for (int i = 0; i < L; ++i) {
            h = (h * a + charToInt(i, haystack)) % modulus;
            ref_h = (ref_h * a + charToInt(i, needle)) % modulus;
        }
        if (h == ref_h) return 0;

        // const value to be used often : a**L % modulus
        long aL = 1;
        for (int i = 1; i <= L; ++i) aL = (aL * a) % modulus;

        for (int start = 1; start < n - L + 1; ++start) {
            // compute rolling hash in O(1) time
            h = (h * a - charToInt(start - 1, haystack) * aL
                    + charToInt(start + L - 1, haystack)) % modulus;
            if (h == ref_h) return start;
        }
        return -1;
    }
}
